
(* 
* 
      
left tree - key - value - right tree - depth 

*)

(*
type key = float

type 'a t =
    Empty
  | Node of 'a t * key * 'a * 'a t * int  

open Map.Make ;;
 
*)




module type OrderedType =
  sig
    type t
    val compare: t -> t -> int
  end


module Make(Ord: OrderedType) = struct

  type key = Ord.t

  type 'a t =
      Empty
    | Node of 'a t * key * 'a * 'a t * int

  type 'a retval =
      ESet of int * int * 'a list (* leq - gt - values *)
	  
  let rec fill_right t = function (* start leftmost *)
    0 -> (0,[])
    | n -> match t with
	Empty -> (0,[])
      | Node(l,v,d,r,_) -> 
	  let (vl,ll) = fill_right l n in
	  if vl == 0 then (0,ll) 
	  else if vl == 1 then (0,ll @ [d])
	  else let (vr,lr) = fill_right r (n - vl - 1)in
	  (vl + vr + 1, ll @ [d] @ lr)

	    
  let rec fill_left t = function (* start rightmost *)
      0 -> (0,[])
    | n -> match t with
	Empty -> (0,[])
      | Node(l,v,d,r,_) -> 
	let (vr,lr) = fill_left l n in
	if vr == 0 then (0,lr) 
	else if vr == 1 then (0,d :: lr)
	else let (vl,ll) = fill_left r (n - vr - 1)in
	(vl + vr + 1, ll @ [d] @ lr)
	  
	  
  let rec find_segment k x = function
    Empty ->
      ESet(0,0,[])
    | Node(l, v, d, r, _) ->
	let c = compare x v in
	if c = 0 then ESet(1,0,[d]) else 
	(* all work in else *)
	if (c < 0) then
	  let (ESet(lc,rc,li)) = find_segment k x l in
	  let (count,seg) = fill_right r (k - rc) in
	ESet(lc,rc + count, li @ seg)
	else
	  let (ESet(lc,rc,li)) = find_segment k x r in
	  let (count,seg) = fill_left l (k - lc) in
	  ESet(lc + count,rc, seg @ li)

end
